package com.lw.leetcode.linked.c;

import com.lw.leetcode.linked.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * sort
 * c
 * 剑指 Offer II 078. 合并排序链表
 * 23. 合并K个升序链表
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/18 15:59
 */
public class MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }
        ListNode node = new ListNode(0);
        ListNode root = node;

        while (!queue.isEmpty()) {
            ListNode poll = queue.poll();
            node.next = poll;
            if (poll.next != null) {
                queue.add(poll.next);
                poll.next = null;
            }
            node = node.next;
        }
        return root.next;
    }

}
